// C/C++的定义链表节点方式
// 单链表
struct ListNode
{
    int val; // 节点上存储的元素
    ListNode* next; // 指向下一个节点的指针
    ListNode(int x): val(x), next(NULL) {} // 节点的构造函数
};
// 如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

// 移除链表元素
class Solution{
public:
    ListNode removeElement(ListNode* head, int val){
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* cur=dummyHead;
        while(cur->next!=NULL){
            if(cur->next->val==val){
                ListNode* tmp=cur->next;
                cur->next=cur->next->next;
                delete tmp;
            }
            else{
                cur=cur->next;
            }
        }
        head=dummyHead->next;
        delete dummyHead;
        return head;
    }
};

// 设计链表
class MyLinkedList(){
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int x)val(x),next(NULL){}
    };

    MyLinkedList(){
        _size=0;
        _dummyHead=new ListNode(0);
    }

    int getIndex(int index){
        if(index<0||index>_size-1)
            return -1;
        ListNode* cur=_dummyHead->next;
        while(index--)
            cur=cur->next;
        return cur->val;
    }
    void addAtHead(int val){
        addAtIndex(0, val);
    }
    void addAtTail(int val){
        addAtIndex(_size, val);
    }
    void addAtIndex(int index, int val){
        if(index>_size)
            return;
        if(index<0)
            index=0;
        ListNode* cur=_dummyHead;
        while(index--)
            cur=cur->next;
        ListNode* toAdd=new ListNode(val);
        toAdd->next=cur->next;
        cur->next=toAdd;
        _size++;
    }
    void deleteAtIndex(int index){
        if(index<0||index>_size-1)
            return;
        ListNode* cur=_dummyHead;
        while(index--)
            cur=cur->next;
        ListNode* tmp=cur->next;
        cur->next=cur->next->next;
        delete tmp;
        tmp=NULL;
        _size--;
    }
private:
    int _size;
    ListNode* _dummyHead;
};

// 反转链表
// 方法一：双指针法
class Solution{
public:
    ListNode* reverseList(ListNode* head){
        ListNode* cur=head;
        ListNode* pre=NULL;
        ListNode* tmp;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            // update
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}
// 方法二：递归法(从后往前翻转)
class Solution{
public:
    ListNode* reverseList(ListNode* head){
        // end condition
        if(head==NULL) return NULL;
        if(head->next==NULL) return head;
        // recursion
        ListNode* last=reverseList(head->next);
        // main
        head->next->next=head;
        head->next=NULL;
        return last;
    }
};

// 两两交换链表中的节点
class Solution{
public:
    ListNode* swapPairs(ListNode* head){
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* cur=dummyHead;
        while(cur->next&&cur->next->next){
            ListNode* tmp=cur->next;
            ListNode* tmp1=cur->next->next->next;

            cur->next=cur->next->next;
            cur->next->next=tmp;
            cur->next->next->next=tmp1;

            cur=cur->next->next;
        }
        ListNode* res=dummyHead->next;
        delete dummyHead;
        return res;
    }
};

// 删除链表的倒数第N个节点
class Solution{
public:
    ListNode* removeN(ListNode* head, int n){
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* fast=dummyHead;
        ListNode* slow=dummyHead;
        while(n--&&fast!=NULL)
            fast=fast->next;
        fast=fast->next;
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;

        return dummyHead->next;
    }
};

// 链表相交

// 环形链表II



